package tianhao.luo.tree.treadedbinarytree;

/**
 * 线索化二叉树
 *
 * @author: tianhao.luo@hand-china.com 2021/6/22  下午8:25
 */
public class ThreadedBinaryTree {

    private HeroNode root;

    // 为了实现线索化,需要创建要给指向当前结点的前驱结点的指针
    // 在递归进行线索化时,pre总是保留前一个结点
    private HeroNode pre = null;

    public ThreadedBinaryTree(HeroNode root) {
        this.root = root;
    }


    /**
     * 对二叉树进行中序线索化
     * @param node
     */
    public void threadedNodes(HeroNode node){
        // 如果node==null,不能线索化
        if (node == null){
            return;
        }
        // 一 先线索化左子树
        threadedNodes(node.getLeft());

        // 二 线索化 当前结点
        // 处理当前结点的前驱结点
        if (node.getLeft() == null){
            // 让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            // 修改当前结点的左指针类型,指向前驱结点
            node.setLeftType(1);
        }

        // 处理上一个结点的后继结点,这是因为当前树是单向的,只能往后找,不能往前找
        // 所以用一个pre来指向上一次操作的元素
        // 处理后继结点,只能等到走到了当前结点的后继结点才方便操作
        if (pre != null && pre.getRight() ==null){
            // 前前驱结点的右指针指向当前结点
            pre.setRight(node);
            pre.setRightType(1);
        }

        // 每处理一个结点后,pre指向当前结点,作为下一次遍历结点的前驱结点
        pre = node;

        // 三 线索化右子树
        threadedNodes(node.getRight());
    }


    // 遍历线索化二叉树的方法
    public void threadedList(){
        // 定义一个变量,存储当前遍历的结点,从root开始
        HeroNode node = root;
        while (node !=null){
            // 循环的找到leftType == 1的结点,第一个找到的就是8这个结点
            // 后面随着遍历而变化,因为当leftType ==1时,说明该结点是按照线索化
            // 处理后的有效结点
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            // 打印当前这个结点
            System.out.println(node);
            // 如果当前结点的右指针,指向的是后继结点,就一直输出
            while (node.getRightType() == 1){
                // 获取到当前结点的后继结点
                node = node.getRight();
                System.out.println(node);
            }
            // 替换这个遍历的结点,为右子树
            node = node.getRight();
        }
    }

    public void preOrder(){
        if (this.root !=null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    public void infixOrder(){
        if (this.root !=null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    public void postOrder(){
        if (this.root !=null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    public HeroNode preOrderSearch(int no){
        if (this.root !=null){
            return this.root.preOrderSearch(no);
        }else {
            System.out.println("二叉树为空");
            return null;
        }
    }

    public HeroNode infixOrderSearch(int no){
        if (this.root !=null){
            return this.root.infixOrderSearch(no);
        }else {
            System.out.println("二叉树为空");
            return null;
        }
    }

    public HeroNode postOrderSearch(int no){
        if (this.root !=null){
            return this.root.postOrderSearch(no);
        }else {
            System.out.println("二叉树为空");
            return null;
        }
    }


    public void deleteNode(int no){
        if (root !=null){
            if (root.getNo() == no){
                root =null;
            }else {
                root.deleteNode(no);
            }
        }else {
            System.out.println("空树");
        }
    }
}
